//单词拆分  力扣139
//完全背包  排列  
class Solution {
public:
	bool wordBreak(string s, vector<string>& wordDict) {
		unordered_set<string> letters(wordDict.begin(),wordDict.end());
		vector<bool> dp(s.size()+1);
		//初始化
		dp[0] = true;
		//递推
		//组成字符串的单词有顺序要求，所以先背包再物品
		for(int i = 1; i <= s.size(); i++)
		{
			for(int j = 0; j < i; j++)
			{
				string word = s.substr(j,i-j);
				if(dp[j] == true && letters.find(word) != letters.end())
					dp[i] = true;
			}
		}
		return dp[s.size()];
	}
};
